\documentclass[E:/GsjzTle/main/main.tex]{subfiles}

\begin{document}

求关于 \(x\) 的同余方程 \(a x \equiv 1 \pmod {b}\)
的最小正整数解，保证有解 (\(2 ≤a, b≤ 2,000,000,000\))

\begin{itemize}
\item
  式子可等价于 \(ax + by = 1\)，然后跑 \(exgcd\) 就好了
\item
  (因为保证有解，所以可以直接跑 \(exgcd\))
\end{itemize}

\begin{lstlisting}
signed main()
{
	ll a , b , x = 0 , y = 0;
	cin >> a >> b;
	exgcd(a , b , x , y);
	cout << (x % b + b) % b << '\n';
	return 0;
}
\end{lstlisting}

\end{document}
